# coding:utf8

import numpy as np
from collections import defaultdict
import matplotlib.pyplot as plt
import pandas as pd

#TODO:ID3改为CART算法   done
G=[0]


def createSet():
    dataSets = [
        [1, 1, 'yes'],
        [0, 0, 'no'],
        [0, 1, 'no'],
        [1, 0, 'no'],
        [1, 1, 'yes'],
        [0, 1, 'no']
    ]
    labels = ['no surfaceing', 'flippers']
    return dataSets, labels


def create_tree(dataSet, labels):
    num_feature = len(dataSet[0]) - 1
    classList = [example[-1] for example in dataSet]
    # 类别相同则停止划分:只剩这一类了
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    if len(dataSet[0]) == 1:  # 特征属性已经用完
        return majorityCnt(classList)
    G[0]+=1
    best_feature = chooseBestfeatureTosplit(dataSet)
    print(f'\ndataset:{dataSet}\n深度为{G[0]}')
    print(f'best_feature:{best_feature}')
    bestFeatureLabel = labels[best_feature]
    myTree = {bestFeatureLabel:{}}

    del labels[best_feature]

    value_feature = set([example[best_feature] for example in dataSet])

    for value in value_feature:
        labelss=labels[:]
        myTree[bestFeatureLabel][value] = create_tree(
                                        splitData(dataSet,best_feature,value),labelss
                                                    )
    return myTree


def majorityCnt(classList):
    """
    属性用完，但类别还没分完，采用多数选举方法 计算节点分类
    :param classList:
    :return:
    """
    order = defaultdict(int)
    for class_ in classList:
        order[class_] += 1
    return max(order)


def chooseBestfeatureTosplit(dataSet):
    """
    针对不同特征选择增益比最大的特征
    :param dataSet:
    :return:
    选择最合适的特征进行分类
    """
    num_sample = len(dataSet)
    ShannoRate = 0.0
    forward_shannon = calShannonEnt(dataSet)
    # 计算特征值共有多少种
    num_feature = len(dataSet[0]) - 1
    index_feature = 0
    for i in range(num_feature):
        # 所有该特征下值
        value_feature = [example[i] for example in dataSet]
        uni_val_fea = set(value_feature)
        # 该特征下的香农熵
        backward_shannon = 0.0
        # 根据该特征划分后 信息增益大，才代表有效
        for value in uni_val_fea:
            subDataset = splitData(dataSet, ax=i, value=value)
            prop = len(subDataset) / num_sample
            # 这是各个特征各个取值下的比例之和
            backward_shannon += prop * calShannonEnt(subDataset)
        temp = forward_shannon - backward_shannon
        if temp > ShannoRate:
            ShannoRate = temp
            index_feature = i
    return index_feature


def splitData(dataSet, ax: int, value):
    """
    按照不同的特征取值划分子集合,pass掉该特征值，才能体现出根据其他特征继续划分子集的特点
    :param dataSet:
    :param ax: 第几特征
    :param value: 具体的特征值
    :return:子集合
    """
    subDataset = list()
    for sample in dataSet:
        if sample[ax] == value:
            tempSample = sample[:ax]
            tempSample.extend(sample[ax + 1:])
            subDataset.append(tempSample)
    return subDataset


# 计算香农熵
def calShannonEnt(dataSet):
    """
    该数据集的香农熵
    :param dataSet:
    :return:
    """
    num_sample = len(dataSet)
    BestEnt = 0.0
    classDict = defaultdict(int)
    for example in dataSet:
        classDict[example[-1]] += 1
    for value in classDict.values():
        prop = value / num_sample
        BestEnt += -(prop * (np.log2(prop)))
    return BestEnt


def retrieveTree(i):
    listOfTrees =[{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}},
                  {'no surfacing': {0: 'no', 1: {'flippers': {0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}}
                  ]
    return listOfTrees[i]


def getNumLeafs(myTree):
    numLeafs =0
    firstStr=list(myTree.keys())[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        # REW:回归巧妙获取子树的叶节点
        if type(secondDict[key]).__name__ == "dict":
            numLeafs+=getNumLeafs(secondDict[key])
        else:
            numLeafs+=1
    return numLeafs

def getTreeDepth(myTree):
    maxDepth=0
    firstStr=list(myTree.keys())[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        # REW:递归巧妙获取子树的叶节点
        if type(secondDict[key]).__name__ == "dict":
            thisDepth=1+getTreeDepth(secondDict[key])
        else:
            thisDepth = 1
        # 因为每个key都要过滤遍
        if thisDepth > maxDepth:maxDepth = thisDepth
    return maxDepth


def anntationPlotTree():
    decisionNode = dict(boxstyle='sawtooth',fc='0.8')
    leafNode = dict(boxstyle='round4',fc='0.8')
    arrow_args = dict(arrowstyle='<-')

    def plotNode(nodeTxt,centerPt,parentPt,nodeType):
        createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
                                xytext=centerPt, textcoords='axes fraction',
                                va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)

    def plotMidText(cntrPt, parentPt, txtString):
        xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0]
        yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1]
        createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)

    def plotTree(myTree, parentPt, nodeTxt):  # if the first key tells you what feat was split on
        numLeafs = getNumLeafs(myTree)  # this determines the x width of this tree
        depth = getTreeDepth(myTree)
        firstStr = list(myTree.keys())[0]  # the text label for this node should be this
        cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.yOff)
        plotMidText(cntrPt, parentPt, nodeTxt)
        plotNode(firstStr, cntrPt, parentPt, decisionNode)
        secondDict = myTree[firstStr]
        plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD
        for key in secondDict.keys():
            if type(secondDict[key]).__name__ == 'dict':  # test to see if the nodes are dictonaires, if not they are leaf nodes
                plotTree(secondDict[key], cntrPt, str(key))  # recursion
            else:  # it's a leaf node print the leaf node
                plotTree.xOff = plotTree.xOff + 1.0 / plotTree.totalW
                plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
                plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
        plotTree.yOff = plotTree.yOff + 1.0 / plotTree.totalD
    def createPlot(inTree):
        fig = plt.figure(1, facecolor='white')
        fig.clf()
        axprops = dict(xticks=[], yticks=[])
        createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)  # no ticks
        # createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses
        plotTree.totalW = float(getNumLeafs(inTree))
        plotTree.totalD = float(getTreeDepth(inTree))
        plotTree.xOff = -0.5 / plotTree.totalW;
        plotTree.yOff = 1.0;
        plotTree(inTree, (0.5, 1.0), '')
        plt.show()
    mytree = retrieveTree(0)
    createPlot(mytree)


def classify(inputTree,featLabels,testVec):
    firstStr = list(inputTree.keys())[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            if type(secondDict[key]).__name__ == 'dict':
                classLabel = classify(secondDict[key],featLabels,testVec)
            else:
                classLabel = secondDict[key]
    return classLabel


def storeTree(inputTree, filename):
    import pickle
    fw = open(filename, 'w')
    pickle.dump(inputTree, fw)
    fw.close()


def grabTree(filename):
    import pickle
    fr = open(filename)
    return pickle.load(fr)

def lense():
    file = r'F:\Resources\Dataset\lenses.txt'
    fr = open(file)
    lenses = [inst.strip().split('\t') for inst in fr.readlines()]
    lensesLabels=['age','prescript','astigmatic','tearRate']
    lensesTree = create_tree(lenses,lensesLabels)

def main():
    dataSet,labels = createSet()
    file = r'D:\hiicy\documents\train_data.xlsx'
    # dataSet = pd.read_excel(file)
    # dataSet.ix[:,-1][dataSet.ix[:,-1]==1]='是'
    # dataSet.ix[:,-1][dataSet.ix[:,-1]==0]='否'

    # labels = dataSet.columns[:-1]
    # dataSet = dataSet.values
    # dataSet = [list(data) for data in dataSet]
    # print(dataSet)
    myTree = create_tree(dataSet,labels)
    print(myTree)
if __name__ == "__main__":
    # main()
    # anntationPlotTree()
    lense()